import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 739. 每日温度
 */
public class Solution_739 {
    /**
     * 方法二：单调栈
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        // 单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减
        // 注意：因为题目求的是天数，栈中存放的是「数组索引」而非元素值
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                // 如果 temperatures[i] > temperatures[prevIndex]，
                // 则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex
                int preIndex = stack.pop();
                ans[preIndex] = i - preIndex;
            }
            // 如果栈为空 或者 temperatures[i] <= temperatures[prevIndex]，将 i 入栈
            stack.push(i);
        }
        return ans;
    }

    /**
     * 方法一：暴力法
     * <p>
     * 时间复杂度：O(n^2)
     * <p>
     * 空间复杂度：O(1)
     */
    public int[] dailyTemperatures1(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (temperatures[j] > temperatures[i]) {
                    ans[i] = j - i;
                    break;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_739 solution = new Solution_739();
        int[] temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };
        int[] ans = solution.dailyTemperatures(temperatures);
        System.out.println(Arrays.toString(ans));
    }
}
